Queues are often used in processing systems for controlling the flow of digital words of data and/or control information between processing circuits. In particular, queues are useful for interfacing circuits operating at different clock speeds. For example, if a source circuit is operating at a clock rate greater than that at which a corresponding receiving circuit is operating, a queue may be used to temporarily store words output from the source circuit until the receiving circuit is reading to input them. A queue may also be used when a source circuit is operating at a clock rate slower than the clock rate at which a corresponding receiving circuit is operating. In this case, as words are output from the source circuitry they are stored in the queue. Then, after a given number of words have been accumulated, output of stored words to the receiving device is enabled.
Typically, a queue is a first-in-first-out device which receives a sequence of words at its input, stores those words as needed, and then outputs the words in the same sequence received. Queues may be constructed in a number of ways, as is known in the art. For example, a queue may be constructed from a series of storage elements similar to a shift register in which data is simply shifted in order through a series of storage elements from input to output. Alternatively, a queue may be constructed as an array of storage elements with input and output pointers moved to store and retrieve data in sequence. When used in interfacing applications such as discussed above, provision is made such that the input of data is timed with the source device clock and the output of data is timed with the receiving device clock.
Significantly, a queue has a finite length; only a given number of words can be queued up at a given time before an overflow occurs. This limitation is usually due to restrictions on the amount of circuitry which is physically available to construct the queue. Thus, timing of the input and output of words from a queue becomes critical, especially in the case where data is received from the source circuit at a clock rate greater than that at which data is being output to the receiving device. The issue of queue overflow becomes even more critical in high performance processing systems where maximizing data/control word flow rates is essential.
Thus, the need has arisen for circuits, systems and methods for preventing queue overflow in high performance processing systems. In particular, a need has arisen for circuits, systems and methods for preventing overflow of queues used to interface circuits and/or subsystems operating at different clock rates. Such circuits, systems and methods should be adaptable to queues of varying lengths as dictated by the available queuing hardware. Further, these circuits, systems, and methods should not unnecessarily complicate the overall system or degrade performance and should be adapted for construction using available circuits and devices.